package C045;

import java.util.HashSet;

/**
 * ClassName: C02
 * Package: C045
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/7 10:47
 * @Version 1.0
 * @Since 1.0
 */
public class C02 {
    public static void main(String[] args) {
//        System.out.println(getHighBit(Integer.MAX_VALUE));
        int[] arr = {14,70,53,83,49,91,36,80,92,51,66,70};
//        int[] arr = {2,4};
        System.out.println(findMaximumXOR(arr));
        System.out.println(findMaximumXOR2(arr));
    }

    // HashSet的解决方式
    public static int findMaximumXOR2(int[] nums) {
        // 寻找最大的数，获取最高位
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(nums[i], max);
        }
        // 获取最高位
        high = getHighBit(max);

        int ans = 0;
        int better = 0;
        int midNum = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int i = high; i > 0; i--) {
            better = ans | (1 << (i - 1));
            set.clear();
            for (int j = 0; j < nums.length; j++) {
                midNum = (nums[j] >> (i - 1)) << (i - 1);
                if (set.contains(midNum ^ better)) {
                    ans = better;
                    break;
                }
                set.add(midNum);
            }
        }


        return ans;
    }

    static int MAXLEN = 3000001;
    static int[][] ele = new int[MAXLEN][2];
    static int cnt;
    static int high; // 最高的位

    public static int findMaximumXOR(int[] nums) {
        // 构建前缀树
        build(nums);

        // 获取最大值
        int ans = Integer.MIN_VALUE;
        // 获取异或的最大值
        for (int i = 0; i < nums.length; i++) {
            ans = Math.max(ans, getXors(nums[i]));
        }
        clear();

        return ans;
    }

    public static void clear() {
        cnt = 0;
        for (int i = 0; i < ele.length; i++) {
            ele[i][0] = ele[i][1] = 0;
        }
    }

    private static void build(int[] nums) {
        // 寻找最大的数，获取最高位
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(nums[i], max);
        }
        // 获取最高位
        high = getHighBit(max);

        // 构建前缀树
        for (int i = 0; i < nums.length; i++) {
            insert(nums[i]);
        }
    }

    // 通过前缀树获取 num的最大的异或值
    private static int getXors(int num) {
        int cur = 0, index, want, status, ans = 0;
        for (int i = high; i > 0; i--) {
            status = (num >> (i - 1)) & 1;
            want = status ^ 1;
            // 无法达到预期
            if (ele[cur][want] == 0) {
                want ^= 1;
            }
            ans = ans | ((status ^ want) << (i - 1));
            cur = ele[cur][want];
        }
        return ans;
    }

    private static void insert(int num) {
        int index, cur = 0, want;
        for (int i = high; i > 0; i--) {
            index = (num >> (i - 1)) & 1;
            if (ele[cur][index] == 0) {
                ele[cur][index] = ++cnt;
            }
            cur = ele[cur][index];
        }
    }

    // 下标从1开始，从右往左第几位(高位)是1
    private static int getHighBit(int max) {
        int bit = 0;
        for (bit = 0; bit < 32; bit++) {
            if (((max << bit) & Integer.MIN_VALUE) != 0) {
                break;
            }
        }
        return 32 - bit;
    }

}
